Skip to content
数组中最大数对和的最小值
概述
给定一个长度为偶数的整数数组，需将所有元素两两配对，每对的和称为“数对和”。任务是在所有可能的配对方案中，找到最大数对和的最小值，并返回该值。
这个问题的标准解法是：先将数组排序，然后让最小的元素与最大的元素配对，次小的与次大的配对，依此类推。所有配对完成之后，取各对和的最大值，即为答案。
基本概念
- 配对（pair）：从数组中取出两个不同元素组成一组，要求每个元素恰好属于一个配对。
- 数对和（pair sum）：一个配对中两个元素的和。
- 最大数对和：所有配对和中数值最大的那一个。
- 最小化最大数对和：调整分组方式，使得最大数对和在全局范围内达到最低。
工作原理
目标是压制配对中的最大值，而不是优化总和。如果让大的元素彼此靠近，就会产生一个极高的数对和，直接抬高结果；只有把大元素和小元素绑在一起，才能拉低最坏情况下的上限。
排序后的数组记为 a[0] ≤ a[1] ≤ ... ≤ a[n-1]。一种直觉的配对方式是相邻成对：(a[0], a[1]), (a[2], a[3])……这时较大的值会集中在靠后的对中，最大数对和容易偏高。
而首尾配对 (a[0], a[n-1]), (a[1], a[n-2])……则是用最小的元素去“消化”最大的元素，依次类推。这种方案保证每个配对内部极差较大，但配对之间的和趋于均衡，最大数对和达到全局最优。
可用交换论证严格说明：假设存在一个最优方案中某对不是“左端配右端”的形式，那么通过交换元素可以在不增加最大和的前提下，将配对结构调整为首尾配对形式。因此，对排序后的数组，max(a[i] + a[n-1-i]) 就是所求的最小最大数对和。
基本用法
先对数组进行升序排序，然后遍历数组的前半部分，计算每个配对的和并记录最大值。
JavaScript (Node.js) 实现
javascript
function minPairSum(nums) {
nums.sort((a, b) => a - b);
let max = 0;
const n = nums.length;
for (let i = 0; i < n / 2; i++) {
const sum = nums[i] + nums[n - 1 - i];
if (sum > max) max = sum;
}
return max;
}Java 实现
java
import java.util.Arrays;
public class Solution {
public int minPairSum(int[] nums) {
Arrays.sort(nums);
int max = 0;
int n = nums.length;
for (int i = 0; i < n / 2; i++) {
int sum = nums[i] + nums[n - 1 - i];
if (sum > max) max = sum;
}
return max;
}
}Python 实现
python
class Solution:
def minPairSum(self, nums: list[int]) -> int:
nums.sort()
n = len(nums)
max_sum = 0
for i in range(n // 2):
pair_sum = nums[i] + nums[n - 1 - i]
if pair_sum > max_sum:
max_sum = pair_sum
return max_sum示例
输入
[3, 5, 2, 3]
排序后得到[2, 3, 3, 5]
首尾配对：2 + 5 = 7，3 + 3 = 6，最大和为7。
若采用相邻配对：(2, 3)和为5，(3, 5)和为8，最大和8，劣于首尾配对。输入
[1, 2, 3, 4]
相邻配对：(1, 2)和(3, 4)，最大和7。
首尾配对：(1, 4)和(2, 3)，最大和5。
注意点
- 起始最大值：题目保证数组元素为正整数，所以最大值的初始值可设为
0。若输入可能含负数，应初始化为-Infinity或第一个配对的和，防止遗漏负的最大值。 - 排序实现的资源消耗：语言内置排序的时间复杂度通常为 O(n log n)，空间复杂度依实现而定，多为 O(log n)（递归栈）或 O(1)（原地排序）。排序的稳定性不影响最终结果。
- 数组遍历边界：由于长度为偶数，
n / 2恰为配对数量，无需处理落单元素。
限制
- 输入长度约束：数组长度必须为偶数，否则题目定义的“配对”无法完整覆盖所有元素。若在应用时遇到奇数长度，需要预先处理或明确行为。
- 元素类型与范围：算法依赖加法运算，因此对过大整数或浮点数溢出问题需要根据语言特性注意。当元素非数值时，排序和加法行为需重新定义。
- 贪心正确性前提：首尾配对的最优性建立在交换论证成立的基础之上。如果问题的约束发生变化（例如每个配对的大小限制、权重分配等），这种简单的贪心结构可能不再适用。
- 性能边界：排序环节是性能瓶颈，当 n 极大时 O(n log n) 无法进一步压缩；若输入已有序或有特殊分布，可考虑计数排序等线性排序优化，但通常输入为通用整数数组，排序不可避免。
应用
这类“最小化最大和”的配对问题常见于负载均衡与任务调度场景。例如，将一批耗时不同的任务两两分配到两台机器上并行执行，每台机器完成所分配两个任务的总时长即为一个“数对和”。希望最慢的机器耗时尽可能短，就等于寻找一种配对，使最大的总耗时最小。排序后首尾配对恰好能平衡轻重任务，避免两个繁重任务集中到同一台机器上，从而压低了完成全部工作的最长时间。
更一般地，任何需要将资源成对组合并控制最差组合代价的场景，都可以用同样的思路建模。该方法在并行处理、网络数据流调度以及某些带宽分配策略中也有类似应用。